package leetcode.hot100;

/**
 * Created on 2021-01-22 。
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 *
 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
 *
 * @author wll 1978992154@qq.com
 */
public class MaxProfit {
    /**
     * 这是暴力循环 时间复杂度是O(n*n)
     * @param prices 数组
     * @return 最大交易额
     */
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j =i+1; j < prices.length; j++) {
                int temp = prices[j] - prices[i];
                if (temp> maxProfit){
                    maxProfit = temp;
                }
            }
        }
        return maxProfit;
    }


    /**
     * 使用动态规划来做 两个变量 一个记录最小值 一个记录最大值
     * @param prices 价格数组
     * @return 最大交易额
     */
    public int maxProfitByDTGH(int[] prices){
        if (prices.length == 0){
            return 0;
        }
        int minPrice = prices[0],maxPrice = 0,sum;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i]-minPrice > maxPrice){
                maxPrice = prices[i]-minPrice;
            }
        }
        return maxPrice;
    }

}
